class Solution(object):
    def numTilePossibilities(self, tiles):
        self.out = set()
        n = len(tiles)
        p = [0] * n

        def search(t, k):
            if k > 0:
                self.out.add(t)
            if k < n:
                for i in range(n):
                    if not p[i]:
                        p[i] = 1
                        search(t + tiles[i], k + 1)
                        p[i] = 0

        search('', 0)
        return len(self.out)
